package fun.codedesign.jdk.math.algorithm.sort;

/**
 * 希尔排序 <br>
 * <pre>
 *     关键在于插入排序的步长问题
 * </pre>
 *
 * @author zengjian
 * @create 2018-06-25 17:14
 * @since 1.0.0
 */
public class ShellSorter implements Sorter {
    @Override
    public void sort(int[] arr) {
        int length = arr.length;
        // 取1/3步长
        int step = length / 3;
        // < 3时，step=1
        step = step == 0 ? 1 : step;
        for (; ; ) {
            for (int i = 0; i < length - step; i += step) {
                int index = -1;
                int temp = arr[i + step];
                for (int j = i; j >= 0; j -= step) {
                    if (arr[j] > temp) {
                        arr[j + step] = arr[j];
                        index = j;
                    }
                }
                if (index != -1) {
                    arr[index] = temp;
                }
            }
            // step最小值为1
            if ((step /= 3) == 0) {
                break;
            }
        }
    }
}
